1. Field of the Invention
The present invention relates generally to data compression and, more particularly, to a method for parallel compression and decompression of multi-byte, or wide, word data. An exemplary embodiment relates the present invention to parallel compression and decompression of primary color data for an implementation in a hard copy apparatus hardware feasible manner without impacting compression ratio or throughput factors.
2. Description of Related Art
It is known in the art to encode a stream of digital data signals (also referred to herein as "data words" or simply "words") into compressed digital code signals. Similarly, decoding of the compressed digital code signals back into the original data is known in the art. The purpose is to effect a savings in the amount of storage required to hold the full data set or to reduce the amount of time required to transmit a given data set (also referred to as "data throughput"). "Compression ratio" is defined as the ratio of the length of the encoded output data to the length of the original input data; the smaller the ratio, the greater the saving in needed storage capacity or reduction in transmission time.
For example, in color laser printing, it is necessary to have an entire page of information in a storage buffer, such as a random access memory ("RAM") integrated circuit, before the printer engine enters a print cycle. Variations of the basic Lev-Zempel data compression technique (see U.S. Pat. No. 4,464,650 (Eastman) and U.S. Pat. No. 4,558,302 (Welch)) are used in compacting the very large amount of data in the digitized, full color image that is to be printed. As print density, dots per inch ("dpi"), increase to improve the print quality, the amount of RAM needed obviously increases. Typically, RAM is a relatively expensive component of the entire system. Moreover, the data stream structure is relatively complex as color data is expressed in tristimulus space values. For example, every picture element, or "pixel," of the image is coded into an 8-bit byte, or word, for cyan, an 8-bit word for yellow, and an 8-bit word for magenta. (The fundamentals of such three-dimensional trichromatic constructs are discussed in the literature, such as Principles of Color Technology, Billmeyer and Saltzman, J. Wiley & Sons, Inc. publ., N.Y., copr 1981 (2d ed.) and Color Science: Concepts and Methods, Quantitative Data and Formulae, by Wyszecki and Stiles, J. Wiley & Sons, Inc. publ., N.Y., copr. 1982 (2d ed.), incorporated herein by reference. A variety of tri-variable color models are described by Foley and Van Dam in Fundamentals of Interactive Computer Graphics, Adison-Wesley Publishing Company at pages 606-621, incorporated herein by reference.)
At first glance, it would appear to be a simple, straightforward task to take three, equal length, data strings representing any multi-variable type data, send each to a separate compressor, store or transmit the compressed variables, then decompress each separately. However, many data compression algorithms employ variable length encoding schemes. (For example, Huffman encoding, first described by David A. Huffman in the IEEE, Proc. IRE, 40(9), 1098-1101 (1952), entitled A Method for the Construction of Minimum-Redundancy Codes, incorporated herein by reference, has variations and uses described in over one hundred U.S. patents.) Thus, each individually coded bit string must be decoded in the same fashion that it was encoded. That is, the decompression must exactly reverse the compression methodology. Additional hardware overhead would be required to write and read from multiple, different memory locations simultaneously.
Another solution would be to combine the compressed output streams into a single record which could be stored in a single location. Tagging every code with extra identifier bits that identify which compression stream a particular string originated from would accomplish this. However, this adversely impacts compression ratio.
Another manner would be to use first-in, first-out ("FIFO") buffering of the data. However, this leads to the need for further, data-dependent hardware and still requires some compensation methodology where variable length encoding is employed. Thus, such a solution is expensive and results in data transmission delays.
Therefore, there is a need for a method and apparatus that will provide parallel processing of multi-variable data compression and decompression within feasible, economically acceptable, design constraints for hardware implementation and which will not affect the compression ratio or data throughput.